/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sqrtx
   @Language: C++
   @Datetime: 16-02-09 05:18
   */

class Solution {
public:
	/**
	 * @param x: An integer
	 * @return: The sqrt of x
	 * Tip: Newton iteration
	 * f'(x) = dy/dx = f(xn)/(xn-xn+1)
	 * ---> xn+1 = xn - f(xn)/f'(xn)
	 * let f(x) = x^2 - y
	 * xn+1 = xn - (xn^2 - y)/(2xn) = (xn + y/xn)/2
	 * until abs(xn+1 - xn) < precision
	 */
	int sqrt(int y) {
		// write your code here
		double r=1.0;
		for(; abs(r*r-y)>1e-1; r=(r+y/r)/2);
		return r;
	}
};
